//几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？ 
//
// 给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。 
//
// 例 1： 
//
// 
//输入: m = 3, n = 3, k = 5
//输出: 3
//解释: 
//乘法表:
//1	2	3
//2	4	6
//3	6	9
//
//第5小的数字是 3 (1, 2, 2, 3, 3).
// 
//
// 例 2： 
//
// 
//输入: m = 2, n = 3, k = 6
//输出: 6
//解释: 
//乘法表:
//1	2	3
//2	4	6
//
//第6小的数字是 6 (1, 2, 2, 3, 4, 6).
// 
//
// 注意： 
//
// 
// m 和 n 的范围在 [1, 30000] 之间。 
// k 的范围在 [1, m * n] 之间。 
// 
// Related Topics 二分查找 👍 266 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _668_KthSmallestNumberInMultiplicationTable {
    public static void main(String[] args) {
        Solution solution = new _668_KthSmallestNumberInMultiplicationTable().new Solution();
        int m = 3;
        int n = 3;
        int k = 5;
        System.out.println(solution.findKthNumber(m, n, k));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public int findKthNumber(int m, int n, int k) {
            int left = 1;
            int right = m * n;
            while (left < right) {
                int x = left + (right - left) / 2;
                int count = count(m, n, x);
                if (count >= k) {
                    right = x;
                } else {
                    left = x + 1;
                }
            }
            return left;
        }
        private int count(int m, int n, int x) {
            int sum = 0;
            for (int i = 1; i <= m; i++) {
                sum += Math.min(n, x / i);
            }
            return sum;
        }
    }

    class Solution1 {
        public int findKthNumber(int m, int n, int k) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    list.add((i + 1) * (j + 1));
                }
            }

            System.out.println(list);
            list.sort((a, b) -> a - b);
            System.out.println(list);
            return list.get(k - 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}